The present invention generally relates to the representation of data in machine readable form, and more particularly to a method and apparatus for encoding and decoding data into a two-dimensional graphic image, such as the two-dimensional bar code PDF417, that can be automatically machine read to obtain the encoded data in both open and closed systems.
In today's high-technology world, more and more operations are being automatically performed by machines and systems. This ever-increasing drive for automation has resulted in a demand for new techniques for encoding data into machine readable form for automatic entry into the various systems and machinery. The data entry may be for such uses as data transmission, operating various machine functions or the identification of persons or items. The various media that carry the data for automatic entry include punch cards, magnetic tapes and discs and magnetic stripes on cards such as credit cards and badges. The systems utilizing the above carriers are in "closed" systems, i.e., the read function is performed within an apparatus or housing and the reading element is in contact or in near-contact with the carrier means during the reading operation.
One method for representing data in a machine readable form is to encode the data into a pattern of indicia having parts of different light reflectivity, for example, bar code symbols. A bar code symbol is a pattern comprised of a series of bars of various widths and spaced apart from one another by spaces of various widths, the bars and spaces having different light reflective properties. The bars represent strings of binary ones and the spaces represent strings of binary zeros. Generally, the bars and spaces can be no smaller than a specified minimum width which is called a "module" or "unit." The bars and spaces are multiples of this module size or minimum width.
Bar code symbols are typically printed directly on the object or on labels that are attached to the object. The bar code symbols are read by optical techniques, such as scanning laser beams or CCD cameras, and the resulting electrical signals are decoded into data representative of the symbol for further processing. Bar code reading systems are known as "open" systems in that the carrier while being read is not sealed, but is read from a distance and without being in physical contact with the scanner.
The conventional bar code described above is "one-dimensional" in that the information encoded therein is represented by the width of the bars and spaces, which extend in a single dimension. Thus, a bar code of a supermarket item, for example, consists of a string of eleven digits which represent an identifying number, but not a description of the item. The remainder of the relevant information, such as the price, name of the product, manufacturer, weight, inventory data, and expiration date, must be obtained from a database using the identification number. Similarly, data encoded onto other media such as credit card magnetic stripes is composed of one or more "one-dimensional" tracks of encoded data.
The use of bar code symbols and magnetically encoded data has found wide acceptance in almost every type of industry. However, the one-dimensional nature of the encoded data limits the amount of information that can be encoded and hence use has been generally restricted to simple digital representations.
There is an increasing need, however, for a system to encode data in machine readable form that allows for an increase in the amount of data encoded into a given space that can be quickly and easily decoded for further processing. In particular, there is a desire to create "portable data files" which provide more than an identification number which is then used as an index to reference a database. The "portable data file" approach is well-suited to applications where it is impractical to store item information in a database or where the database is not readily accessible when and where the bar code is read. For example, information such as the contents of a shipping manifest or an equipment maintenance history could be carried directly on the object without requiring access to a remote database. Similarly, a hospital could use portable data files to put more medical information on patient identification bracelets. In a manufacturing environment, portable data files could be used to keep production records or even to provide instructions to control machine operations. Ideally, such portable data files could contain up to several hundred or more characters in a relatively small area, but still be read from a distance by a hand-held laser scanner.
One approach for increasing the information in machine-readable symbols is to reduce the height of the bar codes and stack the bar codes one on top of each other to create a "stacked" or "two-dimensional" bar code. A major problem in reading two-dimensional symbols, however, is the loss of vertical synchronization. As shown in FIG. 1A, if the data rows are too short or the scan line intersects the row at a large angle, the scan lines will not coincide with the horizontal lines of the pattern. The height of the rows can be increased as shown in FIG. 1B, but this causes an obvious reduction of information density.
A proposed solution to the vertical synchronization problem is to include both row identifiers and local row discriminators in the two-dimensional bar code symbol in order to distinguish between the rows. One such two-dimensional bar code with row identifiers and local row discriminators is PDF417, which was developed by Symbol Technologies, Inc. A more complete description of PDF417 is contained in U.S. patent application Ser. No. 07/461,881, filed Jan. 5, 1990, and assigned to the same assignee as the present invention, which is hereby incorporated by reference.
Even if the symbol is constructed so that the rows can be distinguished from one another, however, there remains the problem of how to decode such a symbol efficiently. In particular, it is not enough for a decoding method or apparatus to simply recognize that a scan line crossed a row boundary.